Real-world, three-dimensional objects, whether with natural form (e.g., geographical, plant, human, or animal-like) or man-imagined form (e.g., sculptures, reliefs, cars, boats, planes, or consumer products) are difficult to scan. This is because of features such as rapidly varying surface normals and surfaces for which a line of sight is difficult because it is partially obscured by other parts of the object.
Scanning machines—also known as digitizing machines—for scanning objects or parts of objects can be categorized into two types—computer numerically controlled (CNC) and manually operated. A scanning machine includes a unit that contains a sensing means commonly referred to as a probe.
Objects or parts of objects can be scanned on CNC scanning machines with a number of computer numerically controlled (CNC) linear and rotating motor-driven axes. Different CNC machines can move/reorient the probe or the object—or both—by a combination of translation and rotation about these axes. Different machine designs are suited to different classes of objects. Probes can be temporarily or permanently attached to most types of CNC machine tool or CNC coordinate measuring machine that can then be used for scanning. As examples, small and simple three-axis CNC milling machines may be used or large, complex five-axis machines may be used. The points captured by CNC machines are usually on a regular grid and the rate varies from around 1 point per second up to around 20,000 points per second, depending on the technology being used, and the object being scanned. The points from these scanning machines are accurate to the order of 0.05 mm. CNC machines with probes scan by executing one or more programs that move the axes of the machine such that there is relative motion between the probe and the object.
CNC machines are expensive, partly because of the incorporation of motors and the associated equipment for assuring precision motion, such as linear guides and drive screws. Few CNC machines are flexible enough so that the probe can be oriented in six degrees of freedom so as to scan the complete surface of a complex object. Even when a CNC machine has six degrees of freedom, it is often not sufficiently flexible so as to position the probe to scan the complete surface of the object without colliding with the object. When the object is a person or expensive, the risk of using a CNC machine may be unacceptable, and there would be a necessity to make a machine to meet both the safety and scanning requirements of the application. The programming of a CNC machine so that the surface of the object is completely scanned without a collision of the probe or machine with the object is often highly complex. Usually, the design of the machine and the degrees of freedom inherent in the design and limitations in the probe design, such as the standoff distance during scanning between the probe and the object, mean that it is impossible to come up with a scanning strategy that will scan the complete surface of the object. It is common that the object has to be manually picked up and replaced in a different position and/or orientation one or more times during scanning. Each time that this occurs, the object has to be reregistered to a uniform coordinate system such that the data from the different scans can be accurately combined.
Manually operated scanning machines can be categorized into three types—horizontal arm machines, multiply-jointed arms, and devices based on remote position-sensing means.
Manually driven, horizontal arm measuring machines usually have three orthogonal axes and are usually based on a traveling column design. These machines are usually quite large, with the bed being at floor level so large items such as cars can easily be moved onto and off of them. Often motors can be engaged on one or more axes to aid the manual movement of the machine. The probe is normally mounted at a fixed orientation on the end of the horizontal arm. This orientation may be changed and various devices may be attached between the end of the horizontal arm and the probe to aid the changing of the orientation, most of these devices having two axes. Horizontal arm machines have the disadvantage of not being able to easily orient the probe in six degrees of freedom. The limited flexibility in the design of a horizontal arm machine makes most of the far side of the object unscannable.
Multiply jointed arms commonly comprise multiple linkages and are available for scanning complex objects. A multiply jointed arm typically has six joint axes, but may have more or less joint axes. At the end of the multiply jointed arm, there is usually a tip reference point—such as a sphere whose center is the reference point, or a cone ending in a point.
Scanning is carried out by bringing the point or sphere into contact with the object being scanned. The computer monitoring the multiply jointed arm then measures the angles at all the joints of the multiply jointed arm and calculates the position of that reference point in space. The direction of the last link in the multiply jointed arm is also calculated. Positions can typically be output continuously at a rate of around 100 points per second, but the rate can be much more or much less. The accuracy is of the order of 0.1 to 0.5 mm. The points from the arm are usually sparse and unorganized. The sparseness and lack of organization of the points make it difficult to provide enough information for constructing a computer model of the object that is of acceptable quality. A multiply jointed arm with multiple linkages has a limited working volume. In general, if a larger working volume is required, the arms become very expensive, less accurate and tiring, and difficult to operate. The limited working volume can be increased by leapfrogging, in which the whole arm/base is moved to access another volume; but this requires a time-consuming system of registering at least three points each time the arm is moved and recombining the data sets from each arm position. Manufacturers of multiply jointed arms provide precalibrated arms and test methods that the user may employ to make sure that the arm is still calibrated to an acceptable accuracy. Such test methods use, for example, the standard tip reference point at the end of the arm and a reference sphere or a ball-bar, which is a rod with two cylindrical cups that has a precise known distance between a home ball and a end of arm ball. As the arm tip at the end of the ball bar is moved on the surface of a spherical domain, the arm records positions that are later compared to a perfect sphere, and error estimates for the arm are output.
Remote position-sensing devices include hand-held devices that transmit or receive position information in a calibrated reference volume using different physical methods, including electromagnetic pulses and sound waves. A hand-held device may be connected to the rest of the system by means of a cable. These devices are prone to generating scanned points with very large errors. Some devices cannot work when the object being scanned has metallic components. They are less accurate than multiply jointed arms, with accuracies of the order of 0.5 mm upwards.
There are three broad categories of scanning probes that could be mounted on the end of a multiply jointed scanning machine—point, stripe, and area probes. Point probes measure a single point at a time and technologies include mechanical contact methods and optical distance measurement methods. Stripe probes measure a number of points in a line, either simultaneously or rapidly in a scanned sequence. The most common stripe technology is laser stripe triangulation. Area probes measure a two-dimensional array of points on a surface, either simultaneously or in a scanned sequence. The most common technologies are interference fringe and multiple stripe projection. Some area methods require the device to be held still for a few seconds during data capture. Stripe and area methods have an in-built speed advantage over point methods, as there is less motion of the probe relative to the object. There are differences between the methods in terms of accuracy and cost, but these do not generalize with category. For example, a particular area technology may be cheaper and more accurate than another point technology.
Means of capturing independent reference/feature points by contact are well known and efficient. Structured light using stripe or area methods is not good at capturing independent feature points because there is no way for the operator to align a known point on the object with a point on the stripe or in the area.
Geometrical errors in the scanning process stem from many sources. CCD cameras can typically capture video at 25 frames per second. One major disadvantage in normal use is that from any given demand for a frame, there is a variability of 40 msecs until the start of capture of that frame. If the probe is being moved at, for example, 100 mm/sec, this can lead to a geometrical error of 4 mm in the probe's data. The duration of frame capture depends upon the shutter speed; e.g., 1/100 sec is 10 msecs. One major disadvantage in normal use is that if the probe is being moved with a slow shutter speed, an additional geometrical error is created. An arm is typically connected to a computer by a serial cable with arms typically generating positions at 125 positions per second as they move. At this rate, there is a variability of 8 msecs between when a position is needed at the computer and when it arrives. This can also introduce a geometrical error when the probe is moving. The total variabilities of the CCD camera and the arm can cause large aggregate errors.
There is a wide range of formats for 3D information in current use. These include the general categories—point formats, polygon formats, and complex surface formats.
Point formats include independent points, lines of points where a plane intersects with a surface, 2.5D areas of points that are commonly known as range images that are single valued in Z and 3D point arrays, which are often generated by medical scanners. The point formats have many standard representations including the Range Image Standard (RIS) resulting from the European ESPRIT Research & Development Project 6911, IGES, and DXF published by AutoDesk, Inc., in the USA.
Polygon formats include polygons of different geometrical forms. Polygons may be 3- or more sided and formats may include mixed numbers of sides or always the same number of sides. Special cases, such as Delaunay triangulation, can specify the positioning of vertices and the relative lengths of the sides of polygons. Standard representations of polygon formats include STL, published by 3D Systems, Inc., in the USA; IGES; OBJ, published by Wavefront, Inc., in the USA; and DXF.
Complex surface formats include Bezier, NURBS, and COONS patches. Standard representations of complex surface formats include IGES, VDA-FS, SET, STEP, and DXF.
The objective of scanning can be simply to gather a number of three-dimensional points on the surface of the object, or it may be to create a computer model in a format that is useful for the application in which the model is to be used. It is generally true that a cloud of points alone is not much use in many applications and that more structure is needed to make a computer model efficient to manipulate in typical applications such as visualization, animation, morphing and surface or solid modeling.
There are often benefits to be gained from reducing the size of the files associated with the model formats. Any file, whatever its format can be compressed using standard reversible utilities, such as PKZIP/PKUNZIP from PKWare in the USA. With 3D point arrays, an octet format can be used to reduce the size of the arrays that represent a surface. An octet format splits a cubic volume into eight, smaller cubes, and only further subdivides cubes by eight if they contain information. An octet format is reversible. Moving from unstructured point representation to polygon or complex surface formats often produces large compressions but relies on approximations, so the process is nearly always irreversible. It is also difficult to automate so as to give good enough results. Chordal tolerancing is a commonly used method of reducing the quantity of discrete points in a 2D or 3D polyline. As an intermediate data structure, it has disadvantages in that the intermediate data structure does not record the orientation of each stripe; it does not record breaks in the data, but assumes that all the points are connected by a surface; and it does not record jumps in the data, such as those caused by occlusions.
Most scans today are carried out using a multiply jointed arm with a tip reference point. It is usual to first mark the object to be scanned with a permanent or temporary marking device, such as an ink pen or scribe, to create a polygonal network of splines. A single point is then scanned at each network intersection. On the computer, the points are linked together into a polygonal structure. The overall process (marking, scanning, and linking) of creating a 3D polygonal model is at a typical rate of 1 point (or vertex on the model) every 3 seconds. In some implementations, the network is not marked on, but appears on a computer display as each point is scanned. With this implementation, the network is built up interactively. This method is suitable for models with a relatively small number of vertices, i.e., hundreds and thousands. The method is very slow, requires skill, patience, and concentration, and is expensive in human time—particularly for large, detailed objects that can take three weeks to scan.
An alternative method of scanning with a multiply jointed arm and contact tip reference point has often been tried, in which independent points are rapidly captured without the aid of a network. The points are then input into a surfacing software package, which then constructs a polygonal network between the points. However, the “polygonization” of unorganized data points is usually very slow, and speed decreases significantly as the number of points increases. The results are usually so poor as to be unacceptable. There is usually a significant amount of hand editing of the data required.
Where a CNC scanning machine is used, the intermediate data structures are usually range images. A number of unregistered range images may be registered, polygonized, and integrated together. The raw data is a number of range images of an object—typically from 5 to 20 in number—with each one either being a cylindrical or a linear range image. The process is not automatic and requires a combination of operator guidance and automated execution of algorithms. The operator first tries to align (i.e., register) the range images to each other on the computer using a graphics display. This process is not accurate and is followed by an automatic least squares fitting process that attempts to adjust the position and orientation of each range image such that they fit together as well as possible. This process is lengthy, often taking hours on a powerful computer. Each range image is then independently polygonized into a network of 2.5D triangular polygons. Finally, the networks of triangular polygons are integrated. The output is a single 3D polygon data set. The process is expensive, both in terms of capital equipment cost and people time. It can take up to two years to become skilled enough to scan objects to produce good enough models. It can work and produce good results for detailed objects.
For smooth objects, where the objective is to create complex surface formats, a coordinate measuring machine with a contact tip reference point is commonly used. It is usual to mark up the object with the desired surface patch boundaries by using a marking device, such as a pen or a scribe. These patch boundaries are then hand digitized with the contact point probe. The software package then generates a CNC scanning program that automatically takes more points along the boundaries and inside the patches. The software then automatically generates a first attempt at the surface model. This method is used because it is quicker and easier for the operator to define patch boundaries that will lead to a surface model with the desired structure before scanning, than to define the patch boundaries after scanning using a software package on a computer with a display showing the scanned points. It can take several days, and often weeks, to create patch boundaries that are usually splines, then create the patches and then trim the patches to form a surface model by using only the scanned points and a computer.
Scanned data points have been displayed in real-time. The display of points has the disadvantage of easily becoming confusing to interpret, and also that the observer does not know when parts of the object's surface have been missed during scanning.